package cn.cxq.learning.tree;

/**
 * 平衡二叉树
 */
public class AverageBinarySortTree {


    private AverageBinarySortNode root;


    public AverageBinarySortNode getRoot() {
        return root;
    }

    public void setRoot(AverageBinarySortNode root) {
        this.root = root;
    }

    /**
     * 中序遍历（正好是升序）
     */
    public void inorderTransversal() {
        if (this.root == null) System.out.println("二叉排序树为空~~~");
        else this.root.inorderTransversal();
    }

    public void add(AverageBinarySortNode binarySortNode) {
        if (this.root == null) {
            this.root = binarySortNode;
        } else this.root.add(binarySortNode);
    }

    public AverageBinarySortNode search(int value) {
        if (this.root == null) {
            return null;
        }

        return this.root.search(value);
    }

    public AverageBinarySortNode searchParent(int value) {
        if (this.root == null || this.root.left == null && this.root.right == null) {
            return null;
        }
        return this.root.searchParent(value);
    }

    public void delete(int value) {
        if (this.root == null) {
            return;
        }
        if (this.root.left == null && this.root.right == null) {
            if (this.root.value == value) this.root = null;
            return;
        }
        AverageBinarySortNode node = search(value);
        AverageBinarySortNode parent = searchParent(value);
        if (node.left == null && node.right == null) {
            if (parent.left == node) parent.left = null;
            else parent.right = null;
        } else if (node.left != null && node.right == null) {
            if (parent.left == node) parent.left = node.left;
            else parent.right = node.left;
        } else if (node.left == null && node.right != null) {
            if (parent.left == node) parent.left = node.right;
            else parent.right = node.right;
        } else {
            AverageBinarySortNode min = node.findMin();

            delete(min.value);

            node.value = min.value;
        }

        this.root.balance();
    }
}

class AverageBinarySortNode {

    int value;
    AverageBinarySortNode left;
    AverageBinarySortNode right;

    public AverageBinarySortNode(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "AverageBinaryNode{" +
                "value=" + value +
                '}';
    }

    public void inorderTransversal() {

        if (this.left != null) this.left.inorderTransversal();

        System.out.println(this);

        if (this.right != null) this.right.inorderTransversal();
    }

    public void add(AverageBinarySortNode binarySortNode) {
        if (this.value > binarySortNode.value) {
            if (this.left == null) this.left = binarySortNode;
            else this.left.add(binarySortNode);
        } else {
            if (this.right == null) this.right = binarySortNode;
            else this.right.add(binarySortNode);
        }

        if ((this.leftHeight() - this.rightHeight()) > 1) {
            if (this.left != null && this.left.rightHeight() > this.left.leftHeight()) {
                this.left.turnLeft();
            }
            this.turnRight();
        }

        if ((this.rightHeight() - this.leftHeight()) > 1) {
            if (this.right != null && this.right.leftHeight() > this.right.rightHeight()) {
                this.right.turnRight();
            }
            this.turnLeft();
        }
    }

    public AverageBinarySortNode search(int value) {

        if (this.value == value) return this;
        else if (this.value > value) {
            if (this.left == null) return null;
            return this.left.search(value);
        } else {
            if (this.right == null) return null;
            return this.right.search(value);
        }
    }

    public AverageBinarySortNode searchParent(int value) {
        if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value))
            return this;
        if (this.value > value) {
            if (this.left != null) return this.left.searchParent(value);
            return null;
        } else {
            if (this.right != null) return this.right.searchParent(value);
            return null;
        }
    }

    /**
     * 返回子树中最小节点
     *
     * @return
     */
    public AverageBinarySortNode findMin() {
        AverageBinarySortNode temp = this;
        while (temp.left != null) temp = temp.left;

        return temp;
    }

    //返回该节点的高度
    public int height() {
        return Math.max(this.left == null ? 0 : this.left.height(), this.right == null ? 0 : this.right.height()) + 1;
    }

    /**
     * 获取该节点左子树的高度
     *
     * @return 该节点左子树的高度
     */
    public int leftHeight() {
        if (this.left == null) return 0;
        return this.left.height();
    }

    /**
     * 获取该节点右子树的高度
     *
     * @return 该节点右子树的高度
     */
    public int rightHeight() {
        if (this.right == null) return 0;
        return this.right.height();
    }

    /**
     * 左旋转
     */
    public void turnLeft() {

        AverageBinarySortNode newLeft = new AverageBinarySortNode(this.value);

        newLeft.left = this.left;

        newLeft.right = this.right.left;

        this.value = this.right.value;

        this.right = this.right.right;

        this.left = newLeft;
    }

    /**
     * 右旋转
     */
    public void turnRight() {

        AverageBinarySortNode newRight = new AverageBinarySortNode(this.value);

        newRight.right = this.right;

        newRight.left = this.left.right;

        this.value = this.left.value;

        this.left = this.left.left;

        this.right = newRight;
    }

    public void balance() {
        if (this.left!=null) this.left.balance();
        if (this.right!=null) this.right.balance();
        if ((this.leftHeight() - this.rightHeight()) > 1) {
            if (this.left != null && this.left.rightHeight() > this.left.leftHeight()) {
                this.left.turnLeft();
            }
            this.turnRight();
        }

        if ((this.rightHeight() - this.leftHeight()) > 1) {
            if (this.right != null && this.right.leftHeight() > this.right.rightHeight()) {
                this.right.turnRight();
            }
            this.turnLeft();
        }
    }
}
